/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {

    public static ListNode removeElements1(ListNode head, int val) {
        //如果不设置虚拟头节点，需要对虚拟头节点进行特殊处理
        //有可能第二个节点也是要删除的元素，这样设置就可以再开始部分把要删除的元素删除
        while (head != null && head.val == val) {
            //绕过要删除的元素
            ListNode delNode = head;
            head = head.next;
            delNode = null;
        }
        //有可能链表中的所有元素都是要删除的节点，
        if (head == null) return null;
        //删除中间的元素
        ListNode pre = head;
        while (pre.next != null) {
            if (val == pre.next.val) {
                ListNode delNode = pre.next;
                pre.next = delNode.next;
                delNode.next = null;
            } else {
                pre = pre.next;
            }
        }
        return head;
    }

    /**
     * 简化版本
     *
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements2(ListNode head, int val) {
        while (head != null && head.val == val) head = head.next;
        if (head == null) return null;
        ListNode pre = head;
        while (pre.next != null) {
            if (val == pre.next.val) pre.next = pre.next.next;
            else pre = pre.next;
        }
        return head;
    }


    /**
     * 调试方式
     * 对于递归函数来说，有一个非常重要的概念，就是深度
     * 函数每调用一次自己，就可以理解为是递归深度加一，递归深度可以很好的帮助我们理解递归
     *
     * @param head 链表头节点
     * @param val  要查找的元素
     * @return
     */
    public static ListNode removeElements(ListNode head, int val) {
        return removeElements(head, val, 0);
    }

    /**
     * @param head
     * @param val
     * @param depth
     * @return
     */
    public static ListNode removeElements(ListNode head, int val, int depth) {
        String depthString = generateDepthString(depth);
        System.out.print(depthString);
        System.out.println("Call: remove " + val + " in " + head);
        if (head == null) {
            System.out.print(depthString);
            System.out.println("Return： " + head);
            return null;
        }
        ListNode res = removeElements(head.next, val, depth + 1);
        System.out.print(depthString);
        System.out.println("After remove  " + val + "");
        ListNode ret;
        if (head.val == val) {
            ret = res;
        } else {
            head.next = res;
            ret = head;
        }
        System.out.print(depthString);
        System.out.println("Return:   " + ret);
        return ret;
    }

    private static String generateDepthString(int depth) {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < depth; i++) res.append("--");
        return res.toString();
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 6, 3, 4, 5, 6};
        ListNode listNode = new ListNode(nums);
        System.out.println("listNode = " + listNode);
        Solution.removeElements(listNode, 6);
        System.out.println("listNode = " + listNode);
    }
}